/*
 *  boolvector.h
 *  vector
 *
 *  Created by Fredrik Gustafsson on 2010-11-29.
 *  Copyright 2010 KTH. All rights reserved.
 *
 */

#include "vector.h"
#include "stdio.h"
#include <math.h>
#include <climits>
#include <iterator>

class Vector<bool>;

struct bit_reference {
	unsigned int* data;
	unsigned int mask;
	bit_reference(unsigned int* _data, unsigned int _mask) : data(_data), mask(_mask) {}
	
	operator bool() const {
		return((*data & mask) != 0);
	}
	
	bit_reference& operator=(bool b) {
		if (b) {
			*data |= mask;
		} else {
			*data &= ~(mask);
		}
		return *this;
	}
};

struct const_bit_reference {
	unsigned int* data;
	unsigned int mask;
	const_bit_reference(unsigned int* _data, unsigned int _mask) : data(_data), mask(_mask) {}
	
	operator bool() const {
		return((*data & mask) != 0);
	}
};

struct const_bit_iterator : public std::iterator<std::random_access_iterator_tag, bool>
{
	unsigned int intsize() const {
		unsigned int _int_size = sizeof(unsigned int);
		return (_int_size*CHAR_BIT);
	}
	
	unsigned int bitsize(unsigned int s) const {
		double _esize = (double)s/intsize();
		unsigned int _size = ceil(_esize);
		return _size;
	}

	typedef bool const_reference;
	typedef int difference_type;
	unsigned int offset;
	unsigned int* data;
	
	const_bit_iterator() : data(NULL), offset(0) {};
	const_bit_iterator(const const_bit_iterator& bi) : offset(bi.offset), data(bi.data) {}
	const_bit_iterator(unsigned int* _data, unsigned int _offset) : data(_data), offset(_offset) {}
	const_bit_iterator operator=(const const_bit_iterator& bi) {
		if (&bi != this) {
			data = bi.data;
			offset = bi.offset;
		}
		return *this;
	}
	
	const_reference operator*() const {
		int int_offset = bitsize(offset+1)-1;
		int bit_offset = intsize()-(offset%intsize())-1;
		return (data[int_offset] & (1 << bit_offset));
	}
	
	const_reference operator[](difference_type i) const {
		int int_offset = bitsize((offset+i)+1)-1;
		int bit_offset = intsize()-((offset+i)%intsize())-1;
		return (data[int_offset] & (1 << bit_offset));
	}
	
	const_bit_iterator& operator++() {
		++offset;
		return *this;
	}
	
	const_bit_iterator operator++(int) {
		return const_bit_iterator(data, offset++);
	}
	
	const_bit_iterator& operator--() {
		--offset;
		return *this;
	}
	
	const_bit_iterator operator--(int) {
		return const_bit_iterator(data, offset--);
	}
	
	const_bit_iterator operator+(const difference_type& i) {
		return const_bit_iterator(data, offset+i);
	}
	
	const_bit_iterator operator-(const difference_type& i) {
		return const_bit_iterator(data, offset-i);
	}
	
	int operator-(const_bit_iterator& bi) {
		if (data != bi.data) {
			return 0;
		}
		return offset-bi.offset;
	}
	
	int operator+(const_bit_iterator& bi) {
		if (data != bi.data) {
			return 0;
		}
		return offset+bi.offset;
	}
	
	const_bit_iterator& operator+=(const difference_type& i) {
		offset+=i;
		return *this;
	}
	
	const_bit_iterator& operator-=(const difference_type& i) {
		offset-=i;
		return *this;
	}
	
	bool operator==(const const_bit_iterator& bi) const {
		return (data == bi.data && offset == bi.offset);
	}
	
	bool operator<(const const_bit_iterator& bi) const {
		return (bi.data == data && offset < bi.offset);
	}
	
	bool operator>(const const_bit_iterator& bi) const {
		return (bi.data == data && offset > bi.offset);
	}
	
	bool operator!=(const const_bit_iterator& bi) const {
		return !operator==(bi);
	}
	
	bool operator<=(const const_bit_iterator& bi) const {
		return !operator>(bi);
	}
	
	bool operator>=(const const_bit_iterator& bi) const {
		return !operator<(bi);
	}
};

struct bit_iterator : public const_bit_iterator
{
	typedef bit_reference reference;
	bit_iterator() : const_bit_iterator() {}
	bit_iterator(const bit_iterator& bi) : const_bit_iterator(bi) {}
	bit_iterator(unsigned int* _data, unsigned int _offset) : const_bit_iterator(_data,_offset) {}
	bit_iterator operator=(const bit_iterator& bi) {
		if (&bi != this) {
			data = bi.data;
			offset = bi.offset;
		}
		return *this;
	}
	
	reference operator*() const {
		int int_offset = bitsize(offset+1)-1;
		int bit_offset = intsize()-(offset%intsize())-1;
		return reference(&data[int_offset], (1 << bit_offset));
	}
	
	reference operator[](difference_type i) const {
		int int_offset = bitsize((offset+i)+1)-1;
		int bit_offset = intsize()-((offset+i)%intsize())-1;
		return reference(&data[int_offset], (1 << bit_offset));
	}
};

template <>
class Vector<bool> {
protected:
	unsigned int intsize() const {
		unsigned int _int_size = sizeof(unsigned int);
		return (_int_size*CHAR_BIT);
	}
	
	unsigned int bitsize(unsigned int s) const {
		double _esize = (double)s/intsize();
		unsigned int _size = ceil(_esize);
		return _size;
	}
public:
	typedef bool value_type;
	typedef bit_reference reference;
	typedef bit_iterator iterator;
	typedef const_bit_iterator const_iterator;
	typedef bool const_reference;
	
	
    explicit Vector(size_t size = 0) : next_index(size), data_size(size) {
		data = new unsigned int[bitsize(size)];
		for (unsigned int i=0; i<bitsize(size); ++i) {
			data[i] = 0;
		}
	}
	
    explicit Vector(size_t size, const bool val) : next_index(size), data_size(size){
		data = new unsigned int[bitsize(size)];
		if (val) {
			for (unsigned int i=0; i<bitsize(size); ++i) {
				data[i] = UINT_MAX;
			}
		} else {
			for (unsigned int i=0; i<bitsize(size); ++i) {
				data[i] = 0;
			}
		}

	}
	
    Vector(const Vector &v) : data_size(v.data_size), next_index(v.next_index) {
		data = new unsigned int[bitsize(data_size)];
		std::copy(v.data, v.data+bitsize(next_index), data);
	}
	
	
    ~Vector() {
		delete[] data;
	}
	
	iterator begin() {
		return iterator(data, 0);
	}
	
	const_iterator begin() const {
		return const_iterator(data, 0);
	}
	
	iterator end() {
		return iterator(data, next_index);
	}
	
	const_iterator end() const {
		return const_iterator(data, next_index);
	}

	reference operator[](const size_t i) {
		return *iterator(data, i);
	}
	
	const_reference operator[](const size_t i) const {
		return *const_iterator(data, i);
	}
	
    Vector<bool> & operator=(const Vector & v) {
		if (&v != this) {
			data_size = v.data_size;
			next_index = v.next_index;
			delete[]data;
			data = new unsigned int[bitsize(data_size)];
			std::copy(v.data, v.data+bitsize(next_index), data); 
		}
		return *this;
	}
	
    void push_back(const bool& b) {
		ensure_space();
		*iterator(data, next_index++) = b;
	}
	
    void clear() {
		next_index = 0;
	}
	
    size_t size() const {
		return next_index;
	}
	
	Vector<bool> operator&(Vector<bool>& vec) {
		if (bitsize(this->data_size) != bitsize(vec.data_size)) {
			return Vector<bool>();
		}
		Vector<bool> ret = *this;
		for (int i = 0; i<bitsize(this->data_size); ++i) {
			ret.data[i] = this->data[i] & vec.data[i];
		}
		return ret;
	}
	
	Vector<bool> operator|(Vector<bool>& vec) {
		if (bitsize(this->data_size) != bitsize(vec.data_size)) {
			return Vector<bool>();
		}
		Vector<bool> ret = *this;
		for (int i = 0; i<bitsize(this->data_size); ++i) {
			ret.data[i] = this->data[i] | vec.data[i];
		}
		return ret;
	}
	
	Vector<bool> operator^(Vector<bool>& vec) {
		if (bitsize(this->data_size) != bitsize(vec.data_size)) {
			return Vector<bool>();
		}
		Vector<bool> ret = *this;
		for (int i = 0; i<bitsize(this->data_size); ++i) {
			ret.data[i] = this->data[i] ^ vec.data[i];
		}
		return ret;
	}
	
	//quick
	unsigned int quick_weight(unsigned int x) {
		register unsigned int y = x - ((x >> 1) & 033333333333) - ((x >> 2) & 011111111111);
		return ((y + (y >> 3)) & 030707070707) % 63;
	}

	//iterate for all the bits
	int iterative_ones(unsigned int n){
		int ones = 0;
		while (n!=0) {
			ones += n & 0x1u;
			n >>= 1;
		}
		return ones;
	}
	
	//iterativly count only the ones
	int only_ones(unsigned int n)  {
		int ones = 0 ;
		while (n)  {
			ones++ ;
			n &= (n - 1) ;
		}
		return ones;
	}
	
	//translates into a single machine instruction
	int hardware_ones(unsigned int n){
		return __builtin_popcount (n);
	}
	
	unsigned int weight_hw() {
		unsigned int ones = 0;
		for (int i = 0; i<bitsize(data_size); ++i) {
			ones+=hardware_ones(data[i]);
		}
		return ones;
	}
	
	unsigned int weight_oo() {
		unsigned int ones = 0;
		for (int i = 0; i<bitsize(data_size); ++i) {
			ones+=only_ones(data[i]);
		}
		return ones;
	}
	
	unsigned int weight_io() {
		unsigned int sum = 0;
		for (int i = 0; i<bitsize(data_size); ++i) {
			sum+=iterative_ones(data[i]);
		}
		return sum;
	}
	
	unsigned int weight_qw() {
		unsigned int sum = 0;
		for (int i = 0; i<bitsize(data_size); ++i) {
			sum+=quick_weight(data[i]);
		}
		return sum;
	}
	
	friend std::ostream& operator<<(std::ostream& os, Vector<bool> v) {
		Vector<bool>::const_iterator it = v.begin();
		while (it<v.end()) {
			std::cout << *(it++);
		}
		std::cout << std::endl;
		return os;
	}
	
	
private:
    size_t data_size;
    size_t next_index;
    unsigned int *data;
    void ensure_space() {
		if(next_index>=data_size) {
			size_t new_size=(data_size!=0)? data_size*2 : 1;
			unsigned int * new_data = new unsigned int[bitsize(new_size)];
			for (int i=data_size; i<bitsize(new_size); ++i) {
				data[i] = 0;
			}
			std::copy(data, data+bitsize(data_size), new_data);
			delete [] data;
			data = new_data;
			data_size = new_size;
		}
	}
};